package 回溯;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 黄金矿工.java
 * @Description TODO
 * @createTime 2020年11月02日 16:48:00
 */
public class 黄金矿工 {
    class Solution {
        //记录每一条路径的最大值
        int res=0;
        public int getMaximumGold(int[][] grid) {

            for(int i=0;i<grid.length;i++){
                for(int j=0;j<grid[i].length;j++){
                    if(grid[i][j]==0){
                        continue;
                    }
                    res=Math.max(res, dfs(i,j,grid,0));
                }
            }
            return res;
        }

        int dfs(int i,int j,int[][] grid,int sum){
            if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]==0){
                return Math.max(res,sum);
            }
            int temp=grid[i][j];
            grid[i][j]=0;

            sum+=grid[i][j];
            dfs(i + 1, j, grid,sum);
            dfs(i - 1, j, grid,sum);
            dfs(i, j + 1, grid,sum);
            dfs(i, j - 1, grid,sum);


            grid[i][j]=temp;

            return sum;
        }
    }

}
